Several types of algorithms such as Dijkstra's algorithm and the A* algorithm are known as path searching algorithms that search for a path from a departure node to a destination node.
In Dijkstra's algorithm, a path (link string) where the sum total cost becomes lowest is searched for on a map which is expressed with links that connect nodes, according to the cost information that is set to the links in advance. On road maps, a departure node, a destination node, intersections, or the like are used as nodes, and roads that connects pairs of intersections are used as links. Moreover, the length of a link, the travel time, or the like are used as a cost of each link.
In Dijkstra's algorithm, nodes adjacent to the departure node are firstly regarded as a group of nodes to be searched, and the node reachable at the lowest cost is selected therefrom and determined to be the searched-for node. Next, the searched-for nodes are excluded from the group of nodes to be searched, and a group of nodes reachable via the searched-for nodes are newly added to the group of nodes to be searched. In so doing, the nodes that have been passed through before the searched-for node is reached are recorded as previously passed-through nodes. At this stage, the departure node is the previously passed-through node. When the searched-for node is not the destination node, a node that is reachable from the departure node at the lowest cost is continuously determined from the group of nodes to be searched. Such a searching process is repeated until the destination node is determined to be the searched-for node. The searching process terminates when the destination node is determined to be the searched-for node, and a path that connects the departure node with the destination node at the lowest cost is obtained by tracking back the previously passed-through nodes in order from the destination node.
FIG. 1 illustrates how the search for nodes progresses in the path searching process where Dijkstra's algorithm is used. In FIG. 1, white dots indicate nodes to be searched, and black dots indicate the searched-for nodes. In “(a)” of FIG. 1, four nodes adjacent to a departure node S are registered as nodes to be searched, and in “(b)” and “(c)” of FIG. 1, two or more nodes adjacent to the searched-for nodes are added as nodes to be searched. Then, the path searching process terminates when there is a match between the searched-for node subsequently registered in “(d)” of FIG. 1 and the destination node G.
In the A* algorithm, the speed of the searching process may be increased if a cost such as a straight-line distance between a node to be searched and a destination node is added when the cost of reaching the node to be searched is calculated.
In Dijkstra's algorithm, if a departure node is far away from a destination node, there will be a lot of cases where the number of nodes to be searched before reaching the destination node becomes too large and the period of time required for the process becomes too long. In consideration of such a problem, a technique is known in which a path is searched for by classifying the roads into two or more levels depending on the type of road and by selecting one level according to the straight-line distance between a departure point and a destination point.
In this technique, for example, the road network composed of expressways and national roads is classified as the highest level, and the road network composed of expressways, national roads, and prefectural roads is classified as the next highest level lower than the highest level. The road network composed of the roads larger than or equal to municipal roads, including expressways, national roads, and prefectural roads, is moreover for example classified as the further next highest level, and all the roads are classified as the lowest level.
In the cases where the straight-line distance between a departure point and a destination point is short, the lowest level as a detailed road network is adopted to search for a path where all the roads are to be considered for travel.
By contrast, in the cases where the straight-line distance is long, the lowest-level road network is firstly adopted to search for a path from a departure point to a tentative departure point on a higher-level road network, and in a similar manner, a path from a destination point to a tentative destination point on a higher-level road network is searched for. Then, a path connecting the tentative departure point and the tentative destination point is searched for on the higher-level road network. As described above, the number of nodes to be searched may be reduced by searching a road network of a level that is suitable for the distance between a departure point and a destination point, and thus the period of time required for the searching process may be reduced. Moreover, incases of long-distance travel, it becomes possible to obtain a path that meets the demand of a general user by searching for a path in which priority is given to wide roads such as national roads instead of minor streets.
Patent Document 1: Japanese Laid-open Patent Publication No. 06-052237
Non-patent Document 1: E. W. Dijkstra, “A Note on Two Problems In Connexion with Graphs”, Numerische Mathematik 1, pp. 269-271, 1959.
Non-patent Document 2: P. E. Hart, N. J. Nilsson, B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”, IEEE Transactions of Systems Science and Cybernetics, Vol. SSC-4, No. 2, pp. 100-107, 1968.